<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Highscore - The Boost C++ Libraries - Containers</title>
<link rel="stylesheet" href="css/highscore.css" type="text/css">
<link rev="made" href="mailto:boris@highscore.de">
<link rel="home" href="frontpage.html" title="The Boost C++ Libraries">
<link rel="up" href="frontpage.html" title="The Boost C++ Libraries">
<link rel="prev" href="parser.html" title="Chapter 12: Parser">
<link rel="next" href="datastructures.html" title="Chapter 14: Data Structures">
<link rel="chapter" href="introduction.html" title="Chapter 1: Introduction">
<link rel="chapter" href="smartpointers.html" title="Chapter 2: Smart Pointers">
<link rel="chapter" href="functionobjects.html" title="Chapter 3: Function Objects">
<link rel="chapter" href="eventhandling.html" title="Chapter 4: Event Handling">
<link rel="chapter" href="stringhandling.html" title="Chapter 5: String Handling">
<link rel="chapter" href="multithreading.html" title="Chapter 6: Multithreading">
<link rel="chapter" href="asio.html" title="Chapter 7: Asynchronous Input and Output">
<link rel="chapter" href="interprocesscommunication.html" title="Chapter 8: Interprocess Communication">
<link rel="chapter" href="filesystem.html" title="Chapter 9: Filesystem">
<link rel="chapter" href="datetime.html" title="Chapter 10: Date and Time">
<link rel="chapter" href="serialization.html" title="Chapter 11: Serialization">
<link rel="chapter" href="parser.html" title="Chapter 12: Parser">
<link rel="chapter" href="containers.html" title="Chapter 13: Containers">
<link rel="chapter" href="datastructures.html" title="Chapter 14: Data Structures">
<link rel="chapter" href="errorhandling.html" title="Chapter 15: Error Handling">
<link rel="chapter" href="castoperators.html" title="Chapter 16: Cast Operators">
<link rel="section" href="containers.html#containers_general" title="13.1 General">
<link rel="section" href="containers.html#containers_array" title="13.2 Boost.Array">
<link rel="section" href="containers.html#containers_unordered" title="13.3 Boost.Unordered">
<link rel="section" href="containers.html#containers_multiindex" title="13.4 Boost.MultiIndex">
<link rel="section" href="containers.html#containers_bimap" title="13.5 Boost.Bimap">
<link rel="section" href="containers.html#containers_exercises" title="13.6 Exercises">
<meta http-equiv="pics-label" content='(pics-1.1 "http://www.icra.org/ratingsv02.html" l gen true for "http://www.highscore.de" r (nz 1 vz 1 lz 1 oz 1 cz 1) gen true for "http://highscore.de" r (nz 1 vz 1 lz 1 oz 1 cz 1))'>
<meta http-equiv="Content-Style-Type" content="text/css">
<meta http-equiv="Content-Script-Type" content="text/javascript">
<link href="http://www.highscore.de/favicon.ico" rel="shortcut icon" type="image/vnd.microsoft.icon">
<script type="text/javascript" src="js/jquery-1.3.2.min.js"></script><script type="text/javascript" src="js/jquery.event.drag-1.5.min.js"></script><script type="text/javascript" src="js/highscore.js"></script>
</head>
<body>
<div lang="en" class="docbook chapter" title="Chapter 13: Containers">
<p class="title">The Boost C++ Libraries</p>
<script type="text/javascript">
          var titlepage = "Front page";
        
      var titles = new Array(titlepage,
      
        "Chapter 1: Introduction",
      
        "Chapter 2: Smart Pointers",
      
        "Chapter 3: Function Objects",
      
        "Chapter 4: Event Handling",
      
        "Chapter 5: String Handling",
      
        "Chapter 6: Multithreading",
      
        "Chapter 7: Asynchronous Input and Output",
      
        "Chapter 8: Interprocess Communication",
      
        "Chapter 9: Filesystem",
      
        "Chapter 10: Date and Time",
      
        "Chapter 11: Serialization",
      
        "Chapter 12: Parser",
      
        "Chapter 13: Containers",
      
        "Chapter 14: Data Structures",
      
        "Chapter 15: Error Handling",
      
        "Chapter 16: Cast Operators",
      
      "");

      
          var titlehtml = "frontpage.html";
        
      var filenames = new Array(titlehtml,
      
        "introduction.html",
      
        "smartpointers.html",
      
        "functionobjects.html",
      
        "eventhandling.html",
      
        "stringhandling.html",
      
        "multithreading.html",
      
        "asio.html",
      
        "interprocesscommunication.html",
      
        "filesystem.html",
      
        "datetime.html",
      
        "serialization.html",
      
        "parser.html",
      
        "containers.html",
      
        "datastructures.html",
      
        "errorhandling.html",
      
        "castoperators.html",
      
      "");

      
      document.open();
      document.write('<form action="" class="toc">');
      document.write('<select size="1" onchange="location.href=options[selectedIndex].value">');
      for (var i = 0; i < titles.length && i < filenames.length; ++i) {
        if (titles[i] != "" && filenames[i] != "") {
          document.write('<option');
          document.write(' value="' + filenames[i] + '"');
          var expr = new RegExp('[/\]' + filenames[i] + '$');
          if (expr.test(location.href)) {
            document.write(' selected="selected"');
          }
          document.write('>' + titles[i] + '<\/option>');
        }
      }
      document.write('<\/select>');
      document.write('<\/form>');
      document.close();
      
    </script><noscript><p class="toc"><a href="toc.html">Table of Contents</a></p></noscript>
<hr class="hrhead">
<h1 class="title">
<a name="containers"></a><small>Chapter 13:</small> Containers</h1>
<hr>
<div class="toc">
<h3>Table of Contents</h3>
<ul>
<li><span class="sect1"><a href="containers.html#containers_general">13.1 General</a></span></li>
<li><span class="sect1"><a href="containers.html#containers_array">13.2 Boost.Array</a></span></li>
<li><span class="sect1"><a href="containers.html#containers_unordered">13.3 Boost.Unordered</a></span></li>
<li><span class="sect1"><a href="containers.html#containers_multiindex">13.4 Boost.MultiIndex</a></span></li>
<li><span class="sect1"><a href="containers.html#containers_bimap">13.5 Boost.Bimap</a></span></li>
<li><span class="sect1"><a href="containers.html#containers_exercises">13.6 Exercises</a></span></li>
</ul>
</div>
<p class="license"><a href="http://creativecommons.org/licenses/by-nc-nd/3.0/" rel="license" target="_top"><img src="img/88x31_cc_logo.gif" alt="" width="88" height="31"></a> This book is licensed under a <a href="http://creativecommons.org/licenses/by-nc-nd/3.0/" rel="license" target="_top">Creative Commons License</a>.</p>
<hr>
<h2 class="title">
<a name="containers_general"></a>13.1 General</h2>
<div class="sect1"><p>This chapter introduces various Boost C++ Libraries defining containers that complement the ones known from the C++ standard. It outlines the usage of containers from Boost.Unordered, added to the C++ standard with Technical Report 1, shows how to define containers using Boost.MultiIndex and explains when to use Boost.Bimap, a library developed with the help of Boost.MultiIndex. The first library introduced, however, is Boost.Array which allows to treat traditional arrays just like containers known from the C++ standard.</p></div>
<hr>
<h2 class="title">
<a name="containers_array"></a>13.2 Boost.Array</h2>
<div class="sect1">
<p>The library <a class="link" href="http://www.boost.org/libs/array/">Boost.Array</a> defines a template class <code class="classname">boost::array</code> in <code class="filename">boost/array.hpp</code>. Using this class, an array can be created that exhibits the same properties as a traditional array in C++. In addition, <code class="classname">boost::array</code> also conforms to the requirements for C++ containers which makes handling such an array as easy as handling a container. In principle, one can think of  <code class="classname">boost::array</code> as the C++ container <code class="classname">std::vector</code> with the sole difference of the number of elements in <code class="classname">boost::array</code> being constant.</p>
<pre class="programlisting">#include &lt;boost/array.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 
#include &lt;algorithm&gt; 

int main() 
{ 
  typedef boost::array&lt;std::string, 3&gt; array; 
  array a; 

  a[0] = "Boris"; 
  a.at(1) = "Anton"; 
  *a.rbegin() = "Caesar"; 

  std::sort(a.begin(), a.end()); 

  for (array::const_iterator it = a.begin(); it != a.end(); ++it) 
    std::cout &lt;&lt; *it &lt;&lt; std::endl; 

  std::cout &lt;&lt; a.size() &lt;&lt; std::endl; 
  std::cout &lt;&lt; a.max_size() &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.2.1/main.cpp">Download source code</a></li></ul>
<p>As seen in the example, the usage of <code class="classname">boost::array</code> is fairly simple and needs no additional explanation since the methods used have the same meaning as their counterparts from <code class="classname">std::vector</code>.</p>
<p>One peculiarity is pointed out in the following example though.</p>
<pre class="programlisting">#include &lt;boost/array.hpp&gt; 
#include &lt;string&gt; 

int main() 
{ 
  typedef boost::array&lt;std::string, 3&gt; array; 
  array a = { "Boris", "Anton", "Caesar" }; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.2.2/main.cpp">Download source code</a></li></ul>
<p>An array of type <code class="classname">boost::array</code> can be initialized just like a traditional C++ array.</p>
<p>Since this container has been added to the C++ standard with Technical Report 1, it can also be accessed via <code class="classname">std::array</code>, defined in <code class="filename">array</code>, if the particular implementation of the C++ standard supports the Technical Report 1 accordingly.</p>
</div>
<hr>
<h2 class="title">
<a name="containers_unordered"></a>13.3 Boost.Unordered</h2>
<div class="sect1">
<p><a class="link" href="http://www.boost.org/libs/unordered/">Boost.Unordered</a> complements the C++ containers <code class="classname">std::set</code>, <code class="classname">std::multiset</code>, <code class="classname">std::map</code> and <code class="classname">std::multimap</code> with four additional classes: <code class="classname">boost::unordered_set</code>, <code class="classname">boost::unordered_multiset</code>, <code class="classname">boost::unordered_map</code> and <code class="classname">boost::unordered_multimap</code>. These classes only differ slightly from the existing containers and even offer a similar interface. In many cases, either one can be used since the resulting application will only be marginally different.</p>
<p>The difference between the containers of the C++ standard and Boost.Unordered is that containers from Boost.Unordered do not sort their elements and thus do not require elements to be sortable. Boost.Unordered makes sense whenever the sortation of stored elements is of no importance.</p>
<p>In order to still find elements quickly, hash values are calculated. Hash values are numbers, uniquely identifying elements within a container, that can be compared more efficiently than other data types such as strings. Since hash values need to be calculated, data types stored inside containers of Boost.Unordered must support calculation of these IDs accordingly. While e.g. <code class="classname">std::set</code> requires elements to be sortable, <code class="classname">boost::unordered_set</code> requires elements to support hash values. Despite this requirement, Boost.Unordered is usually preferred unless a sortation of elements is desired.</p>
<p>The following example outlines the usage of <code class="classname">boost::unordered_set</code>.</p>
<pre class="programlisting">#include &lt;boost/unordered_set.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

int main() 
{ 
  typedef boost::unordered_set&lt;std::string&gt; unordered_set; 
  unordered_set set; 

  set.insert("Boris"); 
  set.insert("Anton"); 
  set.insert("Caesar"); 

  for (unordered_set::iterator it = set.begin(); it != set.end(); ++it) 
    std::cout &lt;&lt; *it &lt;&lt; std::endl; 

  std::cout &lt;&lt; set.size() &lt;&lt; std::endl; 
  std::cout &lt;&lt; set.max_size() &lt;&lt; std::endl; 

  std::cout &lt;&lt; (set.find("David") != set.end()) &lt;&lt; std::endl; 
  std::cout &lt;&lt; set.count("Boris") &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.3.1/main.cpp">Download source code</a></li></ul>
<p>As the example shows, <code class="classname">boost::unordered_set</code> provides similar methods to <code class="classname">std::set</code>. The example could have used <code class="classname">std::set</code> without bigger changes in the source code as well.</p>
<p>The following example uses <code class="classname">boost::unordered_map</code> to store the age of each person in addition to the name.</p>
<pre class="programlisting">#include &lt;boost/unordered_map.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

int main() 
{ 
  typedef boost::unordered_map&lt;std::string, int&gt; unordered_map; 
  unordered_map map; 

  map.insert(unordered_map::value_type("Boris", 31)); 
  map.insert(unordered_map::value_type("Anton", 35)); 
  map.insert(unordered_map::value_type("Caesar", 25)); 

  for (unordered_map::iterator it = map.begin(); it != map.end(); ++it) 
    std::cout &lt;&lt; it-&gt;first &lt;&lt; ", " &lt;&lt; it-&gt;second &lt;&lt; std::endl; 

  std::cout &lt;&lt; map.size() &lt;&lt; std::endl; 
  std::cout &lt;&lt; map.max_size() &lt;&lt; std::endl; 

  std::cout &lt;&lt; (map.find("David") != map.end()) &lt;&lt; std::endl; 
  std::cout &lt;&lt; map.count("Boris") &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.3.2/main.cpp">Download source code</a></li></ul>
<p>As with the example before, there are no major differences between <code class="classname">boost::unordered_map</code> and <code class="classname">std::map</code>. Again, the example could have been implemented using <code class="classname">std::map</code> without any issues.</p>
<p>As mentioned above, Boost.Unordered requires elements stored in the container to support hash values. Miscellaneous data types such as <code class="classname">std::string</code> are supported innately. For user-defined types, a corresponding hash function must be defined manually.</p>
<pre class="programlisting">#include &lt;boost/unordered_set.hpp&gt; 
#include &lt;string&gt; 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &amp;n, int a) 
    : name(n), age(a) 
  { 
  } 

  bool operator==(const person &amp;p) const 
  { 
    return name == p.name &amp;&amp; age == p.age; 
  } 
}; 

std::size_t hash_value(person const &amp;p) 
{ 
  std::size_t seed = 0; 
  boost::hash_combine(seed, p.name); 
  boost::hash_combine(seed, p.age); 
  return seed; 
} 

int main() 
{ 
  typedef boost::unordered_set&lt;person&gt; unordered_set; 
  unordered_set set; 

  set.insert(person("Boris", 31)); 
  set.insert(person("Anton", 35)); 
  set.insert(person("Caesar", 25)); 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.3.3/main.cpp">Download source code</a></li></ul>
<p>The application stores elements of type <code class="classname">person</code> in a container of type <code class="classname">boost::unordered_set</code>. Since the built-in hash function of <code class="classname">boost::unordered_set</code> does not recognize the class <code class="classname">person</code>, hash values cannot be calculated. Without providing an alternative hash function, the corresponding code would not compile.</p>
<p>The name of the hash function to be defined is <code class="function">hash_value()</code>. It takes an object of the data type for which a hash value should be calculated as its sole argument. Since hash values are simple numbers, the return value of the function must be <code class="type">std::size_t</code>.</p>
<p>Whenever a hash value needs to be calculated for an object, <code class="function">hash_value()</code> is called automatically. The Boost C++ Libraries already define this function for various data types such as <code class="classname">std::string</code>. For user-defined types such as  <code class="classname">person</code>, it needs to be defined manually though.</p>
<p>The implementation of <code class="function">hash_value()</code> is usually fairly simple: The hash value is calculated by accessing the individual properties sequentially using the <code class="function">boost::hash_combine()</code> function from the Boost.Hash library defined in <code class="filename">boost/functional/hash.hpp</code>. This header is automatically included if Boost.Unordered is used since all container calculate hash values based on Boost.Hash.</p>
<p>Besides implementing the <code class="function">hash_value()</code> function, user-defined types need to support the comparison of two objects via the <code class="code">==</code> operator. Therefore, <code class="classname">person</code> implements the <code class="methodname">operator==()</code> operator accordingly.</p>
</div>
<hr>
<h2 class="title">
<a name="containers_multiindex"></a>13.4 Boost.MultiIndex</h2>
<div class="sect1">
<p>The <a class="link" href="http://www.boost.org/libs/multi_index/">Boost.MultiIndex</a> library is much more complex than any of the libraries presented thus far. While both Boost.Array and Boost.Unordered offer containers that can be used immediately, Boost.MultiIndex allows to define new containers. Opposed to the containers from the C++ standard, a user-defined container offers not only one perception to the data but can support an arbitrary number of interfaces. For example, one can create a container that assigns values to keys similar to <code class="classname">std::map</code> but also can use the values as keys conversely - something, that without the help of Boost.MultiIndex would require two containers of type <code class="classname">std::map</code> and the overhead of synchronizing the two containers to guarantee data integrity.</p>
<p>The following example defines a new container using Boost.MultiIndex that allows to store the name and age of people. Contrary to <code class="classname">std::map</code>, the container can be searched for both name and age though.</p>
<pre class="programlisting">#include &lt;boost/multi_index_container.hpp&gt; 
#include &lt;boost/multi_index/hashed_index.hpp&gt; 
#include &lt;boost/multi_index/member.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &amp;n, int a) 
    : name(n), age(a) 
  { 
  } 
}; 

typedef boost::multi_index::multi_index_container&lt; 
  person, 
  boost::multi_index::indexed_by&lt; 
    boost::multi_index::hashed_non_unique&lt; 
      boost::multi_index::member&lt; 
        person, std::string, &amp;person::name 
      &gt; 
    &gt;, 
    boost::multi_index::hashed_non_unique&lt; 
      boost::multi_index::member&lt; 
        person, int, &amp;person::age 
      &gt; 
    &gt; 
  &gt; 
&gt; person_multi; 

int main() 
{ 
  person_multi persons; 

  persons.insert(person("Boris", 31)); 
  persons.insert(person("Anton", 35)); 
  persons.insert(person("Caesar", 25)); 

  std::cout &lt;&lt; persons.count("Boris") &lt;&lt; std::endl; 

  const person_multi::nth_index&lt;1&gt;::type &amp;age_index = persons.get&lt;1&gt;(); 
  std::cout &lt;&lt; age_index.count(25) &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.4.1/main.cpp">Download source code</a></li></ul>
<p>As mentioned before, Boost.MultiIndex does not provide specific containers but rather classes to define new containers. Typically, the first step is to design the new container by using <code class="code">typedef</code> to access different classes in Boost.MultiIndex.</p>
<p>A class used for every container definition is <code class="classname">boost::multi_index::multi_index_container</code> defined in <code class="filename">boost/multi_index_container.hpp</code>. Since it is a template class, at least two arguments are required to be passed accordingly. The first argument is the data type the container should store; in the above example a user-defined class named  <code class="classname">person</code>. The second argument is used to denote different indexes the container should provide.</p>
<p>The key advantage of containers based on Boost.MultiIndex is the ability to access data via different interfaces. The number and type of interfaces for a specific container can now be specified at definition. Since the container in the example application allows to search for people either by name or age, two interfaces have been defined. Boost.MultiIndex calls these interfaces indexes which also influenced the name of the libary.</p>
<p>Interfaces are defined with the help of the <code class="classname">boost::multi_index::indexed_by</code> template class. Each interface is passed as an argument accordingly. The example application defines two interfaces of type <code class="classname">boost::multi_index::hashed_non_unique</code> which is defined in <code class="filename">boost/multi_index/hashed_index.hpp</code>. This interface is used if the container should behave just like one from Boost.Unordered, storing the elements internally using a hash value.</p>
<p>The <code class="classname">boost::multi_index::hashed_non_unique</code> class is a template as well and expects a class able to calculate hash values as its sole argument. Since both interfaces of the container should allow to access people by name and age, one interface calculates hash values for the name while the other interface does so for the age, respectively.</p>
<p>Boost.MultiIndex offers the helper template class <code class="classname">boost::multi_index::member</code>, defined in <code class="filename">boost/multi_index/member.hpp</code>, to access a property. As seen in the above example, several arguments have been specified in order to let <code class="classname">boost::multi_index::member</code> know which property of <code class="classname">person</code> should be accessed and which data type the property has.</p>
<p>Even though the definition of  <code class="classname">person_multi</code> looks quite complicated at first: The class itself operates similar to <code class="classname">boost::unordered_map</code> from Boost.Unordered with the decisive difference of allowing to use both the name and the age of a person to search the container.</p>
<p>In order to access any MultiIndex container, the interface for the access must be specified - the sole exception being the first defined interface. If the <var>persons</var> object is directly accessed via  <code class="methodname">insert()</code> or <code class="methodname">count()</code>, the first interface is implicitly used - in the case of the example the hash container for the  <var>name</var> property. If a different interface should be used, it needs to be explicitly selected.</p>
<p>Interfaces are numbered consecutively, starting at index 0 for the first interface. In order to access the second interface in the example, the <code class="methodname">get()</code> method can be used, passing the index of the desired interface as the template argument.</p>
<p>The return value of <code class="methodname">get()</code> looks kind of complicated: It accesses a class of the MultiIndex container named <code class="classname">nth_index</code> which, again, is a template and thus the index of the interface to be used must be specified as the template argument accordingly. This index must be the same as the one passed to the <code class="methodname">get()</code> method. The final step is to access the type definition <code class="type">type</code> of <code class="classname">nth_index</code> using <code class="code">::</code> - <code class="type">type</code> actually represents the type of the corresponding interface.</p>
<p>While the specifics of an interface do not need to be known since it is automatically derived from <code class="classname">nth_index</code> and <code class="type">type</code>, one should still understand what kind of interface is accessed. Given that interfaces are numbered consecutively in the container definition, this can be answered fairly easy given the index that is passed to <code class="methodname">get()</code> as well as <code class="classname">nth_index</code>. <var>age_index</var> in the example is a hash interface as well - accessing people by age.</p>
<p>Since information such as name and age can be keys of the MultiIndex container based on the interface, they cannot be changed arbitrarily any longer. If the age of a person is altered after it has been searched for by name, the interface using the age as the key would not be aware that the key was altered and thus a new hash value needs to be calculated.</p>
<p>Just like the keys in a container of type  <code class="classname">std::map</code> cannot be modified, information stored within a MultiIndex container cannot be modified either. Strictly speaking, all information stored in a MultiIndex container is constant. To avoid deleting and storing altered versions of the information, Boost.MultiIndex offers a couple of useful methods to modify information directly. Since these methods operate on the MultiIndex container itself and no information is modified directly using the corresponding object, the update is safe. All interfaces are notified and can e.g. calculate new hash values.</p>
<pre class="programlisting">#include &lt;boost/multi_index_container.hpp&gt; 
#include &lt;boost/multi_index/hashed_index.hpp&gt; 
#include &lt;boost/multi_index/member.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &amp;n, int a) 
    : name(n), age(a) 
  { 
  } 
}; 

typedef boost::multi_index::multi_index_container&lt; 
  person, 
  boost::multi_index::indexed_by&lt; 
    boost::multi_index::hashed_non_unique&lt; 
      boost::multi_index::member&lt; 
        person, std::string, &amp;person::name 
      &gt; 
    &gt;, 
    boost::multi_index::hashed_non_unique&lt; 
      boost::multi_index::member&lt; 
        person, int, &amp;person::age 
      &gt; 
    &gt; 
  &gt; 
&gt; person_multi; 

void set_age(person &amp;p) 
{ 
  p.age = 32; 
} 

int main() 
{ 
  person_multi persons; 

  persons.insert(person("Boris", 31)); 
  persons.insert(person("Anton", 35)); 
  persons.insert(person("Caesar", 25)); 

  person_multi::iterator it = persons.find("Boris"); 
  persons.modify(it, set_age); 

  const person_multi::nth_index&lt;1&gt;::type &amp;age_index = persons.get&lt;1&gt;(); 
  std::cout &lt;&lt; age_index.count(32) &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.4.2/main.cpp">Download source code</a></li></ul>
<p>Every interface offered by Boost.MultiIndex supports the <code class="methodname">modify()</code> method which operates directly on the container. The object to be modified is passed using an iterator as the first argument. The second argument is a function or function object that expects an object of the type stored in the container as its first argument - in the example of type <code class="classname">person</code>. This function - named <code class="function">set_age()</code> - allows to modify an object in the container.</p>
<p>So far, only one interface has been introduced: <code class="classname">boost::multi_index::hashed_non_unique</code> calculates a hash value for the information that does not have to be unparalleled. In order to guarantee that no information is stored twice, <code class="classname">boost::multi_index::hashed_unique</code> can be used instead. Please note that information cannot be stored if it does not satisfy the requirements of all interfaces of the particular container. If an interface does not allow copies of information, it does not matter whether a different interfaces does allow them as shown in the following example.</p>
<pre class="programlisting">#include &lt;boost/multi_index_container.hpp&gt; 
#include &lt;boost/multi_index/hashed_index.hpp&gt; 
#include &lt;boost/multi_index/member.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &amp;n, int a) 
    : name(n), age(a) 
  { 
  } 
}; 

typedef boost::multi_index::multi_index_container&lt; 
  person, 
  boost::multi_index::indexed_by&lt; 
    boost::multi_index::hashed_non_unique&lt; 
      boost::multi_index::member&lt; 
        person, std::string, &amp;person::name 
      &gt; 
    &gt;, 
    boost::multi_index::hashed_unique&lt; 
      boost::multi_index::member&lt; 
        person, int, &amp;person::age 
      &gt; 
    &gt; 
  &gt; 
&gt; person_multi; 

int main() 
{ 
  person_multi persons; 

  persons.insert(person("Boris", 31)); 
  persons.insert(person("Anton", 31)); 
  persons.insert(person("Caesar", 25)); 

  const person_multi::nth_index&lt;1&gt;::type &amp;age_index = persons.get&lt;1&gt;(); 
  std::cout &lt;&lt; age_index.count(31) &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.4.3/main.cpp">Download source code</a></li></ul>
<p>The container now uses the <code class="classname">boost::multi_index::hashed_unique</code> class as the second interface signifying that no two people can have the same age since otherwise the hash values would be the same.</p>
<p>The application tries to store a person named Anton who is the same age as the already stored person Boris. Since this violates the requirement of having unique hash values for the second interface, the object is not stored in the container accordingly. When searching for people of age 31, the application therefore displays <code class="computeroutput">1</code>; only the person named Boris has been stored.</p>
<p>The following example introduces the remaining three interfaces offered by Boost.MultiIndex: <code class="classname">boost::multi_index::sequenced</code>, <code class="classname">boost::multi_index::ordered_non_unique</code> and <code class="classname">boost::multi_index::random_access</code>.</p>
<pre class="programlisting">#include &lt;boost/multi_index_container.hpp&gt; 
#include &lt;boost/multi_index/sequenced_index.hpp&gt; 
#include &lt;boost/multi_index/ordered_index.hpp&gt; 
#include &lt;boost/multi_index/random_access_index.hpp&gt; 
#include &lt;boost/multi_index/member.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

struct person 
{ 
  std::string name; 
  int age; 

  person(const std::string &amp;n, int a) 
    : name(n), age(a) 
  { 
  } 
}; 

typedef boost::multi_index::multi_index_container&lt; 
  person, 
  boost::multi_index::indexed_by&lt; 
    boost::multi_index::sequenced&lt;&gt;, 
    boost::multi_index::ordered_non_unique&lt; 
      boost::multi_index::member&lt; 
        person, int, &amp;person::age 
      &gt; 
    &gt;, 
    boost::multi_index::random_access&lt;&gt; 
  &gt; 
&gt; person_multi; 

int main() 
{ 
  person_multi persons; 

  persons.push_back(person("Boris", 31)); 
  persons.push_back(person("Anton", 31)); 
  persons.push_back(person("Caesar", 25)); 

  const person_multi::nth_index&lt;1&gt;::type &amp;ordered_index = persons.get&lt;1&gt;(); 
  person_multi::nth_index&lt;1&gt;::type::iterator lower = ordered_index.lower_bound(30); 
  person_multi::nth_index&lt;1&gt;::type::iterator upper = ordered_index.upper_bound(40); 
  for (; lower != upper; ++lower) 
    std::cout &lt;&lt; lower-&gt;name &lt;&lt; std::endl; 

  const person_multi::nth_index&lt;2&gt;::type &amp;random_access_index = persons.get&lt;2&gt;(); 
  std::cout &lt;&lt; random_access_index[2].name &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.4.4/main.cpp">Download source code</a></li></ul>
<p>The <code class="classname">boost::multi_index::sequenced</code> interface allows to treat a MultiIndex container as a list - similar to  <code class="classname">std::list</code>. The interface is fairly simple to use in the definition of the container: No template arguments need to be passed. The objects of type <code class="classname">person</code> are stored exactly in the given order.</p>
<p>By using the <code class="classname">boost::multi_index::ordered_non_unique</code> interface, objects are automatically sorted. This interface requires to specify the sorting criterion while defining the container. The example specifies to sort the objects of type <code class="classname">person</code> by age using the helper class <code class="classname">boost::multi_index::member</code>.</p>
<p><code class="classname">boost::multi_index::ordered_non_unique</code> provides special methods to find specific ranges within the sorted information. Using <code class="methodname">lower_bound()</code> and <code class="methodname">upper_bound()</code>, the application searches for people that are older than 30 but no older than 40 years. These methods are not provided with any other interface since they require the information to be sorted.</p>
<p>The final interface is <code class="classname">boost::multi_index::random_access</code>, allowing to treat the MultiIndex container just like a vector of type <code class="classname">std::vector</code>. The two prominent methods are <code class="methodname">operator[]()</code> and <code class="methodname">at()</code>.</p>
<p>Please note that <code class="classname">boost::multi_index::random_access</code> completely includes the <code class="classname">boost::multi_index::sequenced</code> interface. While using <code class="classname">boost::multi_index::random_access</code>, all methods of <code class="classname">boost::multi_index::sequenced</code> are therefore available as well.</p>
<p>After covering the four interfaces of Boost.MultiIndex, the remainder of this section focuses on the so-called key extractors. One of the key extractors has been introduced so far:  <code class="classname">boost::multi_index::member</code> defined in <code class="filename">boost/multi_index/member.hpp</code>. This helper class is called key extractor since it allows to explicitly specify which property of a class should be used as the key of an interface.</p>
<p>The following example introduces two more key extractors.</p>
<pre class="programlisting">#include &lt;boost/multi_index_container.hpp&gt; 
#include &lt;boost/multi_index/ordered_index.hpp&gt; 
#include &lt;boost/multi_index/hashed_index.hpp&gt; 
#include &lt;boost/multi_index/identity.hpp&gt; 
#include &lt;boost/multi_index/mem_fun.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

class person 
{ 
public: 
  person(const std::string &amp;n, int a) 
    : name(n), age(a) 
  { 
  } 

  bool operator&lt;(const person &amp;p) const 
  { 
    return age &lt; p.age; 
  } 

  std::string get_name() const 
  { 
    return name; 
  } 

private: 
  std::string name; 
  int age; 
}; 

typedef boost::multi_index::multi_index_container&lt; 
  person, 
  boost::multi_index::indexed_by&lt; 
    boost::multi_index::ordered_unique&lt; 
      boost::multi_index::identity&lt;person&gt; 
    &gt;, 
    boost::multi_index::hashed_unique&lt; 
      boost::multi_index::const_mem_fun&lt; 
        person, std::string, &amp;person::get_name 
      &gt; 
    &gt; 
  &gt; 
&gt; person_multi; 

int main() 
{ 
  person_multi persons; 

  persons.insert(person("Boris", 31)); 
  persons.insert(person("Anton", 31)); 
  persons.insert(person("Caesar", 25)); 

  std::cout &lt;&lt; persons.begin()-&gt;get_name() &lt;&lt; std::endl; 

  const person_multi::nth_index&lt;1&gt;::type &amp;hashed_index = persons.get&lt;1&gt;(); 
  std::cout &lt;&lt; hashed_index.count("Boris") &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.4.5/main.cpp">Download source code</a></li></ul>
<p>The key extractor <code class="classname">boost::multi_index::identity</code>, defined in <code class="filename">boost/multi_index/identity.hpp</code>, is used to utilize data types stored in the container as keys. This requires the <code class="classname">person</code> class to be sortable since it is specified as the key for the interface <code class="classname">boost::multi_index::ordered_unique</code>. In the example, this is achieved by providing an overload for the <code class="methodname">operator&lt;()</code> operator.</p>
<p>The header file <code class="filename">boost/multi_index/mem_fun.hpp</code> defines both the <code class="classname">boost::multi_index::const_mem_fun</code> and <code class="classname">boost::multi_index::mem_fun</code> key extractors which can be used to utilize the return value of a method as the key. In the example application, the return value of <code class="methodname">get_name()</code> is used accordingly. <code class="classname">boost::multi_index::const_mem_fun</code> is used for constant methods while <code class="classname">boost::multi_index::mem_fun</code> is used for non-constant methods.</p>
<p>Boost.MultiIndex offers two more key extractors named <code class="classname">boost::multi_index::global_fun</code> and <code class="classname">boost::multi_index::composite_key</code>. While the former can be used for free-standing or static methods, the latter actually allows to design a key extractor comprising of several other key extractors.</p>
</div>
<hr>
<h2 class="title">
<a name="containers_bimap"></a>13.5 Boost.Bimap</h2>
<div class="sect1">
<p>The <a class="link" href="http://www.boost.org/libs/bimap/">Boost.Bimap</a> library is based on Boost.MultiIndex and offers a container that can be used immediately without defining it first. The container is similar to <code class="classname">std::map</code> with the difference of allowing to search for both the key and the value as shown in the following example.</p>
<pre class="programlisting">#include &lt;boost/bimap.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

int main() 
{ 
  typedef boost::bimap&lt;std::string, int&gt; bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  std::cout &lt;&lt; persons.left.count("Boris") &lt;&lt; std::endl; 
  std::cout &lt;&lt; persons.right.count(31) &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.5.1/main.cpp">Download source code</a></li></ul>
<p><code class="classname">boost::bimap</code> is defined in <code class="filename">boost/bimap.hpp</code> and offers two properties <var>left</var> and <var>right</var> that can be used to access the two containers of type <code class="classname">std::map</code> unified by <code class="classname">boost::bimap</code>. While <var>left</var> accesses the container using keys of type <code class="classname">std::string</code>, <var>right</var> use keys of type <code class="type">int</code> instead.</p>
<p>Besides allowing access to the individual records via a left or right container, <code class="classname">boost::bimap</code> allows to view records as relations as shown in the following example.</p>
<pre class="programlisting">#include &lt;boost/bimap.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

int main() 
{ 
  typedef boost::bimap&lt;std::string, int&gt; bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  for (bimap::iterator it = persons.begin(); it != persons.end(); ++it) 
    std::cout &lt;&lt; it-&gt;left &lt;&lt; " is " &lt;&lt; it-&gt;right &lt;&lt; " years old." &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.5.2/main.cpp">Download source code</a></li></ul>
<p>It is not necessary to access records using <var>left</var> or <var>right</var>. By iterating over the records, the left and right container of the individual record is available through the iterator as well.</p>
<p>While <code class="classname">std::map</code> is accompanied by a container named <code class="classname">std::multimap</code> that can store multiple records using the same key, there is no such equivalent for <code class="classname">boost::bimap</code>. This, however, does not mean that storing records using the same key inside a container of type <code class="classname">boost::bimap</code> is not possible. Strictly speaking, the two required template arguments do not specify the data type to store but rather container types used for <var>left</var> and <var>right</var>. If no container type is specified as seen in the example, the container type <code class="classname">boost::bimaps::set_of</code> is used by default which - similar to <code class="classname">std::map</code> - only allows records with unique keys.</p>
<p>The first example for <code class="classname">boost::bimap</code> can be rewritten as follows.</p>
<pre class="programlisting">#include &lt;boost/bimap.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

int main() 
{ 
  typedef boost::bimap&lt;boost::bimaps::set_of&lt;std::string&gt;, boost::bimaps::set_of&lt;int&gt;&gt; bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  std::cout &lt;&lt; persons.left.count("Boris") &lt;&lt; std::endl; 
  std::cout &lt;&lt; persons.right.count(31) &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.5.3/main.cpp">Download source code</a></li></ul>
<p>Besides <code class="classname">boost::bimaps::set_of</code>, other container types exist to customize <code class="classname">boost::bimap</code>.</p>
<pre class="programlisting">#include &lt;boost/bimap.hpp&gt; 
#include &lt;boost/bimap/multiset_of.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

int main() 
{ 
  typedef boost::bimap&lt;boost::bimaps::set_of&lt;std::string&gt;, boost::bimaps::multiset_of&lt;int&gt;&gt; bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  std::cout &lt;&lt; persons.left.count("Boris") &lt;&lt; std::endl; 
  std::cout &lt;&lt; persons.right.count(31) &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.5.4/main.cpp">Download source code</a></li></ul>
<p>The application uses the container type <code class="classname">boost::bimaps::multiset_of</code> defined in <code class="filename">boost/bimap/multiset_of.hpp</code>. It operates similar to <code class="classname">boost::bimaps::set_of</code> with the exception that the key does not need to be unique. Therefore, the example will display <code class="computeroutput">2</code> when searching for people of age 31.</p>
<p>Since <code class="classname">boost::bimaps::set_of</code> is used for containers of type <code class="classname">boost::bimap</code> by default, the header file <code class="filename">boost/bimap/set_of.hpp</code> does not need to be explicitly included. When using other container types, the corresponding header files must be included accordingly though.</p>
<p>Boost.Bimap offers the classes <code class="classname">boost::bimaps::unordered_set_of</code>, <code class="classname">boost::bimaps::unordered_multiset_of</code>, <code class="classname">boost::bimaps::list_of</code>, <code class="classname">boost::bimaps::vector_of</code> and <code class="classname">boost::bimaps::unconstrainted_set_of</code> in addition to the ones shown above. Except for <code class="classname">boost::bimaps::unconstrainted_set_of</code>, all other container types operate just like their counterparts from the C++ standard or Boost.Unordered.</p>
<pre class="programlisting">#include &lt;boost/bimap.hpp&gt; 
#include &lt;boost/bimap/unconstrained_set_of.hpp&gt; 
#include &lt;boost/bimap/support/lambda.hpp&gt; 
#include &lt;iostream&gt; 
#include &lt;string&gt; 

int main() 
{ 
  typedef boost::bimap&lt;std::string, boost::bimaps::unconstrained_set_of&lt;int&gt;&gt; bimap; 
  bimap persons; 

  persons.insert(bimap::value_type("Boris", 31)); 
  persons.insert(bimap::value_type("Anton", 31)); 
  persons.insert(bimap::value_type("Caesar", 25)); 

  bimap::left_map::iterator it = persons.left.find("Boris"); 
  persons.left.modify_key(it, boost::bimaps::_key = "Doris"); 

  std::cout &lt;&lt; it-&gt;first &lt;&lt; std::endl; 
} </pre>
<ul class="programlisting"><li><a class="programlisting" href="src/13.5.5/main.cpp">Download source code</a></li></ul>
<p><code class="classname">boost::bimaps::unconstrainted_set_of</code> can be used to disable one container type of <code class="classname">boost::bimap</code> making it impossible to access <var>right</var> in order to search for people by age. In this particular case, <code class="classname">boost::bimap</code> behaves just like the standard <code class="classname">std::map</code> container.</p>
<p>Nonetheless, the example also shows why it can make sense to prefer <code class="classname">boost::bimap</code> over <code class="classname">std::map</code>. Since Boost.Bimap is based on Boost.MultiIndex, methods known from Boost.MultiIndex are available as well. The example modifies a key using <code class="methodname">modify_key()</code> which is not possible using <code class="classname">std::map</code>.</p>
<p>Please note how the key is modified in detail: A new value is assigned to the current key via <var>boost::bimaps::_key</var> which is a so-called lambda function as introduced in <a class="xref" href="functionobjects.html" title="Chapter 3: Function Objects">Chapter 3, <i>Function Objects</i></a> and is defined in <code class="filename">boost/bimap/support/lambda.hpp</code>.</p>
<p><code class="filename">boost/bimap/support/lambda.hpp</code> also defines  <var>boost::bimaps::_data</var>. The <code class="methodname">modify_data()</code> method modifies a value in a container of type <code class="classname">boost::bimap</code> accordingly.</p>
</div>
<hr>
<h2 class="title">
<a name="containers_exercises"></a>13.6 Exercises</h2>
<div class="sect1">
<p class="solution">
              You can buy 
              <a target="_top" href="http://en.highscore.de/shop/index.php?p=boost-solution">solutions to all exercises</a>
              in this book as a ZIP file. 
            </p>
<ol>
<li class="listitem"><p>Develop an application that assigns employees to departments of a company. Store some example records and search through them to identify the department of a particular employee as well as the number of employees working in a particular department.</p></li>
<li class="listitem"><p>Extend the application by associating numbers to employees. These numbers must be unique in order to identify employees with the same name unambiguously. Search through the example records to display the information of an employee with a specific number.</p></li>
</ol>
</div>
</div>
<hr class="hrfoot">
<p class="copyright">Copyright © 2008-2010 
        <a class="link" href="mailto:boris@highscore.de">Boris Schäling</a>
      </p>
</body>
</html>
